/**
 * 365. 水壶问题
 * https://leetcode-cn.com/problems/water-and-jug-problem/
 */
public class Solutions_365 {
    public static void main(String[] args) {
//        int x = 3, y = 5, z = 4;  // output: true
        int x = 2, y = 6, z = 5;  // output: false

        boolean result = canMeasureWater(x, y, z);
        System.out.println(result);
    }

    /**
     * 解题思路：数学法（贝祖定理/裴蜀定理）
     * 若 x，y 可以组成 z，则 (x, y) 的最大公约数 g 一定可以被 z 整除，即 z % g == 0
     */
    public static boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
        if (targetCapacity == 0) {
            return true;
        }
        if (jug1Capacity + jug2Capacity < targetCapacity) {
            return false;
        }
        int gcd = gcd(jug1Capacity, jug2Capacity);
        return targetCapacity % gcd == 0;
    }

    /**
     * 计算得到 x 与 y 的最大公约数
     */
    public static int gcd(int x, int y) {
        int z = x % y;
        while (z != 0) {
            x = y;
            y = z;
            z = x % y;
        }
        return y;
    }
}
